home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 7830 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.8 KB
  1. Path: anvil.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: line intersection in C
  5. Date: 27 Feb 1996 12:18:28 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4gvoukINNbdl@anvil.ugrad.cs.ubc.ca>
  8. References: <1996Feb25.230142.29689@dcs.warwick.ac.uk>
  9. NNTP-Posting-Host: anvil.ugrad.cs.ubc.ca
  10.  
  11. In article <1996Feb25.230142.29689@dcs.warwick.ac.uk>,
  12. Daniel Castillo Molero <D.C.Molero@dcs.warwick.ac.uk> wrote:
  13. >
  14. >Hello,
  15. >
  16. >I wonder if anybody can help me to find an algorithm in C to detect whether
  17. >two line segments intersect properly (I don't know if this is the correct
  18. >terminology, but by proper intersection I mean that the intersection is
  19. >not in the extreme of any of them and that one does not lie on top of
  20. >the other).
  21.  
  22. Ask on comp.graphics.algorithms. Read FAQ first. This is a fairly
  23. straightforward linear algebra problem.
  24.  
  25. >I need to test intersection just for line segments whose slope is a multiple
  26. >of 45 degrees, which I suppose may simplify the solution.
  27.  
  28. This admits lines that have infinite slope, so you have to use an implicit
  29. representation of a line:
  30.  
  31.     Ax + By - C = 0.
  32.  
  33. This way you never have to deal with problems like infinite slopes. Any line
  34. can be represented with finite A, B, and C.
  35.  
  36. The two lines intersect if the dot product of (A1, B1) and (-B2, A2) is not
  37. zero. (A1, B1) is a vector perpendicular to one line, (-B2, A2) is a vector in
  38. the direction of one line. If the dot product is zero, they are at 90 degrees
  39. and hence the lines are parallel. Otherwise, they intersect.
  40.  
  41. The fact that they are multiples of 45 degrees might help you in finding the
  42. actual intersection point in particular if the lines lie along some fixed
  43. lattice grid, but you only asked how to check whether they
  44. intersect or not. :)
  45. -- 
  46.  
  47.